package cn.good.yan.sf.t1;

/**
 * 1. 二分查找
 * 一个数据里，查询该下标的位置，如果查询不到，就找到在哪个下标下进行插入
 *
 * @author shengren.yan
 * @create 2024-04-12
 */
public class Demo2 {

    /**
     * 二分查找法： - 查询该下标的位置，如果查询不到，就返回要插入下标的位置
     *
     * @param arr    数组，（升序/降序）
     * @param target 要查询到值
     * @return int 查询到会返回（该值的下标），没有查询到返回（要插入下标的值）
     */
    private static int binarySearchD(int[] arr, int target) {
//        int[] arr = {1, 2, 5, 6, 7};  8
        int i = 0;
        int j = arr.length - 1;
        while (i <= j) {
            int m = (j + i) / 2;
            if (target < arr[m]) {
                j = m - 1;
            } else if (target > arr[m]) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return i;
    }

    /**
     * 二分查找法： - 查询该下标的位置，最靠左的下标
     *
     * @param arr    数组，（升序/降序）
     * @param target 要查询到值
     * @return int 查询到会返回（该值的下标），没有查询到返回（-1）
     */
    private static int binarySearchLeft(int[] arr, int target) {
//      int[] arr = {1, 2, 3, 4, 4, 4, 5, 6};  // 4
        int i = 0;
        int j = arr.length - 1;
        int c = -1;  // 默认是-1，没有找到
        while (i <= j) {
            int m = (j + i) / 2;
            if (target < arr[m]) {
                j = m - 1;
            } else if (target > arr[m]) {
                i = m + 1;
            } else {
                j = m - 1;
                c = m;
            }
        }
        return c;
        //       0   8   m = 4  值 4
        // =4    0   3   m = 1  值 2
        // >4    2   3   m = 2  值 3
        // >4    3   3   m = 3  值 4
        // =4    3   2   终止循环
    }

    /**
     * 二分查找法： - 查询该下标的位置，最靠右的下标
     *
     * @param arr    数组，（升序/降序）
     * @param target 要查询到值
     * @return int 查询到会返回（该值的下标），没有查询到返回（-1）
     */
    private static int binarySearchRight(int[] arr, int target) {
//      int[] arr = {1, 2, 3, 4, 4, 4, 5, 6};  // 4
        int i = 0;
        int j = arr.length - 1;
        int c = -1;  // 默认是-1，没有找到
        while (i <= j) {
            int m = (j + i) / 2;
            if (target < arr[m]) {
                j = m - 1;
            } else if (target > arr[m]) {
                i = m + 1;
            } else {
                i = m + 1;
                c = m;
            }
        }
        return c;
        //       0   8   m = 4  值 4
        // =4    5   8   m = 6  值 5
        // <4    5   5   m = 5  值 4
        // =4    6   5   终止循环
    }

    public static void main(String[] args) {
        // 数组
        int[] arr = {1, 2, 3, 4, 4, 4, 5, 6};
        int i = binarySearchRight(arr, 4);
        System.out.println(i);
    }


}
